package org.usmile.algorithms.learn.tree;

/**
 * 二叉查找树
 */
public class RecursionBinarySearchTree<E extends Comparable<E>> {
    private TreeNode<E> root;

    private int size;

    public RecursionBinarySearchTree() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void add(E e) {
        root = add(root, e);
    }

    private TreeNode<E> add(TreeNode<E> node, E e) {
        if (node == null) {
            size++;

            return new TreeNode<>(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else {
            node.right = add(node.right, e);
        }

        return node;
    }

    public boolean contains(E e) {
        return find(e) != null;
    }

    private TreeNode<E> find(E e) {
        return find(root, e);
    }

    private TreeNode<E> find(TreeNode<E> node, E e) {
        if (node == null) {
            return null;
        }

        if (e.compareTo(node.e) == 0) {
            return node;
        } else if (e.compareTo(node.e) < 0) {
            return find(node.left, e);
        } else {
            return find(node.right, e);
        }
    }

    public E getMin() {
        if (root == null) {
            return null;
        }

        return getMin(root.left).e;
    }

    private TreeNode<E> getMin(TreeNode<E> node) {
        if (node.left == null) {
            return node;
        }

        return getMin(node.left);
    }

    public E getMax() {
        if (root == null) {
            return null;
        }

        return getMax(root).e;
    }

    private TreeNode<E> getMax(TreeNode<E> node) {
        if (node.right == null) {
            return node;
        }

        return getMax(node.right);
    }

    public E removeMin() {
        if (root == null) {
            return null;
        }
        E min = getMin();
        root = removeMin(root);

        return min;
    }

    private TreeNode<E> removeMin(TreeNode<E> node) {
        if (node.left == null) {
            TreeNode<E> right = node.right;
            node.right = null;
            size--;

            return right;
        }
        node.left = removeMin(node.left);

        return node;
    }

    public E removeMax() {
        if (root == null) {
            return null;
        }
        E max = getMax();
        root = removeMax(root);

        return max;
    }

    private TreeNode<E> removeMax(TreeNode<E> node) {
        if (node.right == null) {
            TreeNode<E> left = node.left;
            node.left = null;
            size--;

            return left;
        }
        node.right = removeMax(node.right);

        return node;
    }

    public void remove(E e) {
        root = remove(root, e);
    }
    // 在以 node 为根节点的子树中删除节点 e
    // 并且返回删除后的子树的根节点
    private TreeNode<E> remove(TreeNode<E> node, E e) {
        if (node == null) {
            return null;
        }

        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);

            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);

            return node;
        } else {
            // 要删除的节点就是 node
            if (node.left == null) {
                TreeNode<E> rightNode = node.right;
                node.right = null;
                size--;

                return rightNode;
            }

            if (node.right == null) {
                TreeNode<E> leftNode = node.left;
                node.left = null;
                size--;

                return leftNode;
            }

            // node 的 left 和 right 都不为空
            TreeNode<E> successor = getMin(node.right);

            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = null;
            node.right = null;
            // bug 修复：这里不用修改 size 了，因为在上面的 removeMin 已经修改过了
            // size--;
            return successor;
        }
    }


    public static void main(String[] args) {
        RecursionBinarySearchTree<Integer> tree = new RecursionBinarySearchTree<>();
        tree.add(1);
        tree.add(2);
        tree.add(-1);
        tree.add(-2);
        TreeUtil.print(tree.root);

        System.out.println(tree.getMin());
        System.out.println(tree.getMax());
        System.out.println(tree.removeMin());
        TreeUtil.print(tree.root);
        System.out.println(tree.removeMax());
        TreeUtil.print(tree.root);
    }
}
